package leetcode;

/**
 * Created with IntelliJ IDEA.
 * Description:剑指 Offer 36. 二叉搜索树与双向链表
 * User: 东莞呵呵
 * Date:2022-07-21
 * Time:21:09
 */
public class TestDemo9 {
    public Node treeToDoublyList(Node root) {
        if(root==null){
            return null;
        }
        treeToDoublyListChild(root);

        Node head = root;
        while(head.left != null) {
            head = head.left;
        }
        return head;
    }
    public Node prev=null;
    public void treeToDoublyListChild(Node root){
        if(root==null){
            return;
        }

        treeToDoublyListChild(root.left);
        root.left=prev;
        if(prev!=null){
            prev.right=root;
        }
        prev=root;
        treeToDoublyListChild(root.right);

    }
}

class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
